1. Field of the Invention
The present invention relates to a method and an apparatus for packet scheduling for determining a sequence of reading a plurality of packets stored in a network apparatus in a network.
In recent years, the spread of multimedia and real-time applications etc. utilizing networks has led to a demand for guaranteeing the quality of service (QoS) provided by those networks. A network apparatus such as router, switch, and the like in this network requires a means for classifying packets into a plurality of queues in accordance with the type of the traffic and controlling the transfer of the packets while guaranteeing the quality of service (QoS) required for each queue. This means is a packet scheduling apparatus.
2. Description of the Related Art
Some factors for determining packet scheduling, that is, a sequence of reading packets guaranteeing the quality of service, can be considered. Particularly effective determinative factors are known to be bandwidth guarantee and preferential control.
Here, “bandwidth guarantee” means the guarantee of a bandwidth to be permitted for traffic, for example 100 Mbps, based on a reservation from a user.
On the other hand, “preferential control” means that, when the bandwidth is not reserved, not performing so-called best effort transfer, but giving a priority order to a plurality of traffic, based on a designation by a user, from traffic of a high priority to traffic of a low priority and, when the packets to be transferred are generated, reading out any packets to be transferred from the higher priority order of traffic to which those packets belong.
Accordingly, a packet scheduling apparatus has to read out packets while guaranteeing the reserved bandwidth and giving preference to traffic of a high priority order over traffic of a low priority order.
Conventionally, as a method of packet scheduling, “packet fair queuing” has been used. This packet fair queuing sets a weight based on the bandwidth reserved for every queue. If there is remaining bandwidth unused in the packet transfer, the remaining bandwidth is effectively utilized by being fairly reallocated according to the weight of every queue. Below, a detailed explanation will be given based on this packet fair queuing.
A well known method for realizing packet fair queuing is based on the method referred to as “Generalized Processor Sharing discipline” (GPS discipline) disclosed in a Reference 1 (A. K. Parekh and R. G. Gallager, “A Generalized Processor Sharing Approach to Flow Control in Integrated Service Networks: The Single-Node Case”, IEEE/ACM Trans. on Networking, vol. 1, pp. 344-357, June 1993).
This GPS discipline is known as an ideal fluid model for packet fair queuing. This fluid model assumes that the coverage of service can be divided infinitely and that accordingly all flows (flows at the application level, for example, file transfer) can be serviced in parallel. However, a packet cannot be divided, therefore a plurality of packets cannot be simultaneously serviced. For this reason, in actual packet scheduling, a method approximating the GPS discipline is used. Note that, in the present invention, the term “packet fair queuing” is used as a generic term for methods of packet scheduling approximating the GPS discipline.
As one method of packet fair queuing, the method of packet scheduling referred to as weighted fair queuing (WFQ) is well known. This is used by computing a “service finish time” prescribed in the GPS discipline. This WFQ is disclosed in detail in Reference 1, but will be simply explained here.
The packets forming the flows are stored in queues corresponding to the flows. When representing each of these queues as a queue i (i=1, 2, 3, . . . ), a weight φi proportional to the bandwidth reserved for the queue i is set for the queue i. Further, the sum of the weights of queues in a backlog state is defined as φb. Here, when packets to be transmitted are stored in a queue, that queue is referred to as being in a “backlog state” or is referred to as an “active” one.
When using these φi, and φb, a variable Fi of each queue is computed as in the following equation (2) by r_i (outgoing rate after reallocation of packets of Qi) of the following equation (1). Fi (finish_i) is the service finish time.r—i=φi×R/φb  (1)Fi=max(t—i, F′i)+Li/ri  (2)
Note that, in equations (1) and (2), R represents the rate of an outgoing link, t_i an arrival time of a header packet of the queue i, Li a packet length of the header packet of the queue i, F′i the service finish time of the packet immediately before the packet to be output from now on, and max(t_i, F′i) a larger of t_i and F′i.
In WFQ, the header packet stored in the queue i having the minimum Fi among the Fi′s computed by equation (2) is selected as a packet to be output next.
As mentioned above, in the method of packet scheduling by the conventional packet fair queuing wherein the packets to be output next are selected from among a plurality of queues i as mentioned above, the weights φi of the packet fair queuing are set as follows.
First, a weight φi is set for each traffic requesting a bandwidth guarantee based on the ratio of the bandwidths reserved for each traffic.
On the other hand, for traffic requesting preferential control, the weight φi of the low priority traffic is set smaller than the weight φi of the high priority traffic. By setting the weights in this way, the reserved bandwidth can be guaranteed for traffic requesting a bandwidth guarantee. On the other hand, high priority traffic is allocated bandwidth (φi) larger than that for the low priority traffic and preferentially output.
Note that, as another conventional packet fair queuing, the method of packet scheduling referred to as “self clocked fair queuing” (SCFQ) using a virtual clock to modify the WFQ to suppress the amount of computation has been proposed in Reference 2, S. Golestani, “A Self-Clocked Fair Queuing Scheme for Broadband Applications”, In Proc. of INFOCOM 94, pp. 636-646, 1994. A similar method referred to as a “virtual clock” is proposed in Reference 3, L. Zhang, “Virtual Clock: A New Traffic Control Algorithm for Packet Switching Networking”, In Proc. of SIGCOMM'90, pp. 19-29, 1990. The algorithm using this virtual clock can be applied in the present invention as well. This will be mentioned later as a second embodiment.
Summarizing the problems to be solved in the invention, in the method of packet scheduling by the conventional packet fair queuing, the packets of traffic are output according to only the bandwidth (φi) set in advance for the traffic. Accordingly, packets of low priority traffic are output according to the reserved bandwidth irrespective of if packets of high priority traffic are stored in queues. For this reason, there are cases where packets of high priority traffic which originally must be output first are output after the packets of low priority traffic. As a result, the order of output of the high priority packets and the low priority packets are reversed. When viewing this in the unit of packets, there was a problem in that the high priority traffic could not preferentially receive service relative to the low priority traffic.